With the development of location-based services and the popularity of various mobile devices such as cellular phones, PDAs, and GPS-enabled devices, large amounts of data with spatial contexts have become available. Examples of such data with spatial contexts include geographic search logs comprising keywords with associated locations, and GPS logs that maintain latitude, longitude, and velocity information.
Co-location pattern discovery is directed towards processing data with spatial contexts to find classes of spatial instances that are frequently located together. Examples of such spatial instances include businesses listed in yellow page-like databases and queries on geographical search engines. For example, a co-located query pattern may be {“shopping mall”, “parking”}, because people often search for the terms “shopping mall” and “parking” over locations that are geographically close to one another.
Discovering spatial co-location patterns has useful applications; for instance, co-located queries discovered from search logs can help with query suggestion, location recommendation, and targeted local advertising. However, previous co-location pattern mining techniques are not scalable for a large data set, such as geographic search logs and GPS logs. One reason is that a large number of expensive join operations are required to generate co-location instances, primarily due to the way in which a co-location instance set is scanned, typically in its entirety.